package leetcode._07_贪心;

import org.junit.Test;

/**
 * @author pppppp
 * @date 2022/3/22 8:50
 * 当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
 * <p>
 * 给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
 * <p>
 * 示例 1:
 * <p>
 * 输入: n = 10
 * 输出: 9
 * 示例 2:
 * <p>
 * 输入: n = 1234
 * 输出: 1234
 * 示例 3:
 * <p>
 * 输入: n = 332
 * 输出: 299
 *  
 * 提示:
 * 0 <= n <= 109
 */
public class _738_单调递增的数字 {

    /*找到 n[i] > n[i+1] 的位置 然后变为 n[i]-1/9  如 32 ——> 29 然后再整体来判断新数字是否是升序的*/
    @Test
    public void T_0() {
        int[] nums = {110,10, 1234, 332};
        int[] ans = {99,9, 1234, 299};
        for (int i = 0; i < nums.length; i++) {
            // System.out.println(monotoneIncreasingDigits(nums[i]) == ans[i]);
            System.out.println(monotoneIncreasingDigits_review(nums[i]) == ans[i]);
        }
    }

    /*递归 找到第一个下降的数据 将其由 ij 变为 (i-1)9*/
    public int monotoneIncreasingDigits_review(int n) {
        String strn = String.valueOf(n);
        char[] ch = strn.toCharArray();
        for (int i = 0; i < ch.length-1; i++) {
            if(ch[i+1] < ch[i]){
                String pre = strn.substring(0, i);
                int times = strn.length()-i-1,after = Integer.valueOf(ch[i] - '0');
                while (times > 0){
                    after *= 10;
                    times--;
                }
                after--;
                String afterStr = String.valueOf(after);
                /*补零*/
                if(afterStr.startsWith("9") && pre.length() != 0){
                    afterStr =  "0" + afterStr;
                }
                return monotoneIncreasingDigits_review(Integer.valueOf(pre + afterStr));
            }
        }
        return n;
    }
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) > s.charAt(i+1)) {
                String s1 = s.substring(0, i) + (Character.getNumericValue(s.charAt(i)) - 1);
                StringBuilder sb = new StringBuilder();
                int cnt = s.length() - s1.length();
                while (cnt > 0) {
                    sb.append("9");
                    cnt--;
                }
                if (Integer.valueOf(s1) > 0) {
                    String s2 = s1 + sb;
                    return monotoneIncreasingDigits(Integer.valueOf(s2));
                } else {
                    return monotoneIncreasingDigits(Integer.valueOf(String.valueOf(sb)));
                }
            }
        }
        return n;
    }
}
